/*
  滑动窗口思路：
    - 初始化window窗口为长度为0
    - 不断的将right指针向右移动 当window中包含所有的目标字符时则为初步完成
    - 下一步进行优化，将left指针移动，也就是缩小窗口值，left向右移动
    - 直到window不再满足时结束
说明：window是当前已经遍历了的存储结果,needs是我们需要的实际结果，只要window包含needs那么就是第一步完成
*/
/*
  @params {string} s
  @params {string} t
  @return {string}
  */
const minWindow = (s, t) => {
  // 将need和window初始化
  const needs = new Map()
  const window = new Map()
  for (let c of t) {
    needs.set(c, needs.has(c) ? needs.get(c) + 1 : 1)
  }
  // 初始化left和right指针,[left,right)
  let left = right = 0
  // 记录最小覆盖子串的起始索引
  let start = 0, len = Infinity

  // valid表示当前窗口中已经满足了几项值
  let valid = 0

  // 当right指针指向最后时跳出
  while (right < s.length) {
    const c = s[right]
    right++
    // 更新window窗口,必须要needs中包含当前内容才更新window窗口
    if (needs.has(c)) {
      if (window.has(c)) {
        window.set(c, window.get(c) + 1)
      } else {
        window.set(c, 1)
      }
      if (window.get(c) === needs.get(c)) valid++
    }


    // 判断window窗口是否需要收缩，也就是left是否需要向右移动
    // 如果当前window中满足的项数等于needs的长度那么则说明第一步完成
    while (valid === needs.size) {
      if (right - left < len) {
        start = left
        len = right - left
      }
      // 将window的最左侧移出窗口
      let d = s[left]
      // 缩小窗口
      left++
      // 进行窗口更新
      if (needs.get(d)) {
        if (window.get(d) === needs.get(d)) valid--
        window.set(d, window.get(d) - 1)
      }
    }

  }
  return len === Infinity ? '' : s.substr(start, len)

}
console.log(minWindow('FDSFJkjKfdjkABfjdksfaCBA', 'ABC'))
